#include <iostream>

using namespace std;

const int N = 2e3 + 10;

typedef long long LL;

LL f[N][N];
LL g[N][N];

int t, k;

void get_c()
{
	for(int i = 0; i <= 2000; i++)
	{
		f[i][0] = 1;
		for(int j = 1; j <= i; j++)
		{
			f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % k;
			g[i][j] = (f[i][j] == 0 ? 1 : 0) + g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
		}
		g[i][i + 1] = g[i][i];
	}
}

int main()
{
	cin >> t >> k;
	get_c();
	while(t--)
	{
		int x, y; cin >> x >> y;
		cout << g[x][min(x, y)] << endl;	
	}	
	return 0;
}
 
